function [nodes] = clonalg(gen, N, n, beta, d)
%
% Função CLONALG
% Roda o Algoritmo de Seleção Clonal para otimização do TSP
% Para o problema, a função afinidade é inversa. Quanto menor seu valor, maior a afinidade do Ab
%
% Copyrigth by Luiz Otávio Vilas Bôas Oliveira
% May, 2011
%
	% Entrada de dados do arquivo
	filePath = input('Entre com o caminho para o arquivo .tsp: ');
	nodes = readTSPFile(filePath);
	% Inicializa a população de anticorpos
	ab = initializeAbs(size(nodes,1), N); 
	% Roda o algoritmo por gen gerações
	for i=1:gen
		ab = decode(ab, nodes); % Decodifica
		abN = select(ab, n); % Select
		c = clone(N, abN, beta); % Clona
		cStar = hypermutation(c); % Hypermut
	end
	nodes = c;
end

% Clona (reproduz) os elementos da população Ab{n} proporcionalmente à afinidade f e a um fator multiplicativo β, gerando uma população C
function c = clone(N, abN, beta)
	Nc = 0;
	n = size(abN,1);
	% Calcula a quantidade de clones serão gerados para alocar memória
	for i=1:n
		Nc = Nc + round(beta * N / i);
	end
	c = cell(Nc, 2);
	count = 1;
	for i=1:n
		% Calcula a quantidade de clones para aquele indivíduo
		Nc = round(beta * N / i);
		for j=1:Nc
			c(count,:) = abN(i,:);
			count = count + 1;
		end
	end
end

% Seleciona n anticorpos da população Ab com maior afinidade (menor distância)
function abListN = select(abList, n)
	indexes = sortrowsc(cell2mat(abList(:,2)));
	abListN = cell(n,2);
	for i=1:n
		abListN(i,:) = abList(indexes(i),:);
	end
end

% Decodifica e calcula a afinidade f da população AbList
function abList = decode(abList, nodes)
	stopCriteria = size(abList, 1);
	for i=1:stopCriteria
		abList{i,2} = calculateAffinity(abList{i,1}, nodes);
	end
end

% Função responsável por gerar a primeira população de anticorpos
function abList = initializeAbs(L, n)
	abList = cell(n,2);
	for i=1:n
		ab = zeros(L,1);
		chosenElements = zeros(L,1);
		% Gera L índices
		for j=1:L;
			% Escolhe um elemento qualquer do conjunto e guarda seu índice
			choose = ceil(rand*L);
			if chosenElements(choose) == 0
				% Sinaliza os elementos já escolhidos
				chosenElements(choose) = 1;
				ab(j) = choose;
			% Se o elemento selecionado já tiver sido escolhido, escolhe o próximo não escolhido
			else
				while chosenElements(choose) == 1  
					choose = choose + 1;
					if choose > L
						choose = 1;
					end
				end
				chosenElements(choose) = 1;
				ab(j) = choose;
			end
		end
		% Adiciona o anticorpo à lista
		abList{i,1} = ab;
	end
end

% Função responsável por calcular a afinidade de um anticorpo
function aff = calculateAffinity(ab, nodes)
	L = size(ab,1);
	aff = 0;
	for i=1:L-1
		a = nodes(ab(i),:);
		b = nodes(ab(i+1),:);
		aff = aff + euclideanDistance(a,b);
	end
	a = nodes(ab(L),:);
	b = nodes(ab(1),:);
	aff = aff + euclideanDistance(a,b);
end

% Calcula a distância euclideana entre dois pontos
function dist = euclideanDistance(a,b)
	squareSum = 0;
	numDim = size(a,2);
	for i=1:numDim
		squareSum = squareSum + (a(i)-b(i))^2;
	end
	dist = sqrt(squareSum);
end

% Função responsável por recuperar os dados a partir de um arquivo retirado do site TSPLib
function [nodes] = readTSPFile(filePath)
	txt = textread(filePath, '%s', 'delimiter', '');
	[truefalse, start] = ismember('NODE_COORD_SECTION', txt);
	[truefalse, endPoint] = ismember('EOF', txt);
	nodes = zeros(endPoint - start - 1,2);
	for i = start+1:endPoint-1
		info = strread(txt{i});
		nodes(info(1),:) = [info(2) info(3)];
	end
end
